<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Burst Balloon Dynamic Programming</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="burst-balloon-dynamic-programming">Burst Balloon Dynamic Programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=IFNibRVgFBo&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=29">https://www.youtube.com/watch?v=IFNibRVgFBo&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=29</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/BurstBalloons.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/BurstBalloons.java</a></li>
<li><a href="https://leetcode.com/problems/burst-balloons/">https://leetcode.com/problems/burst-balloons/</a></li>
<li><a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/za-qi-qiu">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/za-qi-qiu</a></li>
</ul>
<p>Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.</p>
<p>Find the maximum coins you can collect by bursting the balloons wisely.</p>
<p>Note:</p>
<pre><code><code><div>You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --&gt; [3,5,8] --&gt;   [3,8]   --&gt;  [8]  --&gt; []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
</div></code></code></pre>
<p>本题，tushare roy的视频讲解 不如labuladong的清晰。 下面是4种解法</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache
<span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxCoins</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        nums = [<span class="hljs-number">1</span>] + [i <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> nums <span class="hljs-keyword">if</span> i &gt; <span class="hljs-number">0</span>] + [<span class="hljs-number">1</span>]   <span class="hljs-comment"># 这里的优化很巧妙</span>
        n = len(nums)
        
        <span class="hljs-comment"># (0) bruce top-down</span>
        <span class="hljs-comment"># ans = 0</span>
        <span class="hljs-comment"># def _dfs(vals, score):</span>
        <span class="hljs-comment">#     nonlocal ans</span>
        <span class="hljs-comment">#     if len(vals) == 2:</span>
        <span class="hljs-comment">#         ans = max(ans, score)</span>
        <span class="hljs-comment">#         return</span>
        <span class="hljs-comment">#     n = len(vals)</span>
        <span class="hljs-comment">#     for i in range(1, n-1):</span>
        <span class="hljs-comment">#         _dfs(vals[:i]+vals[i+1:], score + vals[i-1]*vals[i]*vals[i+1])</span>
        <span class="hljs-comment"># _dfs(nums, 0)</span>
        <span class="hljs-comment"># return ans</span>
    
        
        <span class="hljs-comment"># (1) top -&gt; bottom + memo</span>
        <span class="hljs-comment">#@lru_cache(None)</span>
        <span class="hljs-comment">#def _dfs(i, j):</span>
        <span class="hljs-comment">#    if i+1 == j:</span>
        <span class="hljs-comment">#        return 0</span>
        <span class="hljs-comment">#</span>
        <span class="hljs-comment">#    ans = 0</span>
        <span class="hljs-comment">#    for k in range(i+1, j):</span>
        <span class="hljs-comment">#        ans = max(ans, nums[i]*nums[k]*nums[j] + _dfs(i,k) + _dfs(k,j))</span>
        <span class="hljs-comment">#    return ans</span>
        <span class="hljs-comment">#</span>
        <span class="hljs-comment">#return _dfs(0, n-1)</span>
        
        <span class="hljs-comment">#</span>
        <span class="hljs-comment"># 下面是 bottom -&gt; top, dp 的三种方式</span>
        <span class="hljs-comment">#</span>
        <span class="hljs-comment">#  https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/za-qi-qiu</span>
        <span class="hljs-comment"># 我们有3种选择        </span>
        <span class="hljs-comment"># </span>
        <span class="hljs-comment"># 像（2）那样斜着遍历</span>
        <span class="hljs-comment"># 像（3） 从左到右逐列遍历，每一列遍历的时候，从下往上遍历</span>
        <span class="hljs-comment"># 像（4） 从下往上逐行遍历，每一行遍历的时候，从左往右遍历</span>
        <span class="hljs-comment">#</span>
        <span class="hljs-comment"># (2) 斜着遍历</span>
        <span class="hljs-comment"># dp = [[0] * n for _ in range(n)]  </span>
        <span class="hljs-comment"># for gap in range(2, n):  # 必须这样斜着遍历才行</span>
        <span class="hljs-comment">#     for i in range(n-gap):</span>
        <span class="hljs-comment">#         j = i + gap</span>
        <span class="hljs-comment">#         for k in range(i+1, j):</span>
        <span class="hljs-comment">#             dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])</span>
        <span class="hljs-comment">#             #print(f"{i} {j} {k}")</span>
        <span class="hljs-comment">#             #pprint(dp)</span>
        <span class="hljs-comment"># return dp[0][n-1]</span>
    
        <span class="hljs-comment"># (3) 从左到右逐列遍历，每一列遍历的时候，从下往上遍历</span>
        <span class="hljs-comment"># dp = [[0] * n for _ in range(n)] </span>
        <span class="hljs-comment"># for j in range(0, n):</span>
        <span class="hljs-comment">#     for i in range(j, -1, -1):</span>
        <span class="hljs-comment">#         for k in range(i+1, j):</span>
        <span class="hljs-comment">#             dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])</span>
        <span class="hljs-comment"># return dp[0][n-1]</span>
    
        <span class="hljs-comment"># (4) 从下往上逐行遍历，每一行遍历的时候，从左往右遍历</span>
        dp = [[<span class="hljs-number">0</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)] 
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n):
                <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(i+<span class="hljs-number">1</span>, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
        <span class="hljs-comment"># pprint(dp, width=40)</span>
        <span class="hljs-comment"># [[0, 0, 3, 30, 159, 167],</span>
        <span class="hljs-comment"># [0, 0, 0, 15, 135, 159],</span>
        <span class="hljs-comment"># [0, 0, 0, 0, 40, 48],</span>
        <span class="hljs-comment"># [0, 0, 0, 0, 0, 40],</span>
        <span class="hljs-comment"># [0, 0, 0, 0, 0, 0],</span>
        <span class="hljs-comment"># [0, 0, 0, 0, 0, 0]]</span>
       
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">0</span>][n<span class="hljs-number">-1</span>]
    
</div></code></pre>

    </body>
    </html>